\chapter{Probl\'ematique et pr\'esentation g\'en\'erale de PosNet} \label{chap:Probl\'ematiques et pr\'esentation g\'en\'erale de PosNet}
\minitoc
\ochap{}{}
%\lhead[\fancyplain{}{}]%    
 % {\fancyplain{}{\bfseries Posnet : the big picture}}%\setcounter{equation}{0}


%\section{Vue d'ensemble de PosNet} [TODO \`a r\'ediger]

% Le chapitre "Pr\'eliminaires" a expos\'e une vue de type \og bo\^ite noire \fg{} d'un index distribu\'e. La pr\'esente section r\'ev\`ele la mise-en-oeuvre par PosNet des fonctionnalit\'es 
% d'indexation et de localisation. 

%\ochap{L}{e} pr\'esent chapitre est en deux parties. 
%La section \ref{sec:Probl\'ematique} reprend le contexte et les objectifs de mani\`ere synth\'etique et pr\'esente, \`a la lumi\`ere de l'\'etat de l'art effectu\'e au chapitre pr\'ec\'edent,
% la d\'emarche adopt\'ee, les probl\'ematiques scientifiques adress\'ees et les contributions attendues. 
%Puis la section \ref{sec:Pr\'esentation g\'en\'erale de la solution propos\'ee} pr\'esente une vue g\'en\'erale de la solution propos\'ee, PosNet : l'architecture, le fonctionnement 
%g\'en\'eral et la structure de donn\'ees principale. Cette structure de donn\'ees, appel\'ee pograph, fait partie des contributions de cette th\`ese. 
\ochap{N}{ous} avons dans le chapitre \ref{chap:Indexation et localisation dans les syst\`emes distribu\'es \`a grande \'echelle} \'enonc\'e les cinq crit\`eres requis par notre solution et pr\'esent\'e un \'etat de l'art des travaux permettant de r\'epondre partiellement \`a ces crit\`eres. Nous exposons dans ce qui suit la probl\'ematique trait\'ee dans cette th\`ese et donnons une pr\'esentation g\'en\'erale de la solution propos\'ee : PosNet. 

\section{Probl\'ematique et contributions} \label{sec:Probl\'ematique et contributions}

%\chapter{Probl\'ematique et contributions / TODO a integrer dans presentation PosNet sous forme de <<Motivations>> ? } \label{problematique-contributions}
%\minitoc
%\ochap{}{}

%
%\subsection{Objectifs de PosNet}
%
%Soit le corps d'hypoth\`eses suivant : 
%\begin{itemize}
%\item Machines reli\'ees par infrastructures de communication existante
%\item Domaine d'administration unique, au sein du quel tous les noeuds sont suppos\'es de confiance
%\item Mod\`ele de donn\'ees : mod\'elisables par vecteurs ; attributs ind\'ependents ; no need for hierarchical namespaces or complex relational schemas
%%\item NO stringent latency requirements => queries CAN be routed through multiple nodes (and tolerate variability in response time)
%\end{itemize}
%En admettant ce syst\`eme d'hypoth\`eses, PosNet affiche les objectifs suivants par-rapport aux solutions d\'ecentralis\'ees de stockage 
%de donn\'ees pr\'esent\'ees ci-avant :
%
%\paragraph{Un mod\`ele de donn\'ees multi-dimensionnel sans hachage}
%PosNet s'adresse \`a des application ayant besoin d'un mod\`ele de donn\'ees riche (au-de\`a des simples cha\^i nes de caract\`eres). C'est le cas des applications 
%manipulant des donn\'ees qui sont repr\'esent\'ees par des tuples cl\'e-valeur (ou des vecteurs). 
%Or les overlays P2P structur\'es n'autorisent que les donn\'ees uni-dimensionnelles. Lorsqu'ils g\`erent les donn\'ees 
%multi-dimensionnelles, c'est de mani\`ere non native (\'elaboration de surcouches et d\'ecomposition de requ\^e tes sur plusieurs attributs en requ\^e tes sur un attribut unique)
%
%\paragraph{Un mod\`ele de requ\^e au-del\`a des requ\^e tes exactes, d\'edi\'e aux requ\^e tes comparatives}
%PosNet s'adresse \`a des applications ayant besoin d'un mod\`ele de requ\^e tes riches (au-del\`a des requ\^e tes exactes). C'est le cas de toute application ayant besoin
%d'effectuer des requ\^etes par plages de valeurs (dont le traitement est intrins\`equement peu efficace dans les syst\`emes reposant sur le hachage des donn\'ees). 
%Or les data store sont d\'edi\'es au traitement efficace de requ\^e tes exactes, tout comme les overlays P2P structur\'es. 
%
%PosNet d'adresse \`a des applications int\'eress\'ee par des requ\^e tes comparatives, de type : par plages de valeurs, inclusion, front de Pareto... 
%C'est le cas d'applications ayant une approche exploratoire de leurs donn\'ees : recherchant non pas tant une donn\'ee connue a priori, qu'\`a extraire de l'information
%sur les don\'ees en tant qu'ensemble (quel est l'ensemble des donn\'ees contenues dans tel sous-ensemble ? quel est l'ensemble des n donn\'ees maximisant tel attribut ? quel
%est l'ensemble des donn\'ees qui ne sont domin\'ees par aucune autre sur l'ensemble de leurs attributs ? etc.)
%Or si l'on consid\`ere les bases de donn\'ees relationnelles, dont la s\'emantique des requ\^e tes SQL est la expressive parmi les exemples cit\'es, 
%la prise en charge de requ\^etes de type skyline reste un domaine ouvert de recherche 
%
%\paragraph{Une architecture auto-organisante, la parall\'elisation des traitements, l'absence de SPF}
%PosNet s'adresse \`a des applications b\'en\'eficiant d'une d\'ecentralisation compl\`ete, aussi bien des donn\'ees que des traitements (de contr\^ ole et de requ\^e tes). 
%C'est le cas notamment pour : 
%\begin{itemize}
%\item Les applications qui ne peuvent se permettre un data center => pr\'f\'erence pour une mutualistion des ressources de particuliers
%\item Les applications qui ont des contraintes fortes de confidentialit\'e => contr\^o le local des donn\'ees, absence de single point of failure
%\item Les applications qui ont des contraintes de perfomances => parall\'elisation des traitements
%\item ... 
%\end{itemize}
%Or les bases de donn\'ees distribu\'ees centralisent les traitements. 
%
%PosNet s'adressent \`a des applications requ\'erant une infrastructure de stockage auto-organisante. Il s'agit de minimiser les interventions humaines, notamment lors d'un
%redimensionnement du syst\`eme : int\'egration \`a la vol\'ee de ressources suppl\'ementaires (cf. Bigtable -> very small incremental cost for new services and expanded computing power)
%C'est le cas des applications dont les besoin en ressources sont dynamiques : il faut qu'une 
%Or les techniques de sharding, si elles permettent aux bases de donn\'ees de passer \`a l'\'echelle, n\'cessitent
%un partitionnement des donn\'ees "\`a la main" \`a chaque expansion. 
%
%\paragraph{Un taux de recall optimal}
%PosNet s'adressent \`a des applications requ\'erant des garanties en termes de taux de pr\'ecision et de recall. 
%Les overlays P2P non-structur\'es ne le permettent pas, dues aux protocoles d'inondation employ\'es dans le routage des requ\^e tes . 
%
%TRANSITION
%On a vu qu'aucune des solutions dans l'existant, tel que pr\'esent\'e dans cet \'etat de l'art, ne satisfait l'ensemble des objectif que l'on se pose.
%
%Les probl\'ematiques non abord\'ees en l'\'etat par PosNet : 
%\begin{itemize}
%\item PosNet a \'et\'e pens\'e pour \^e tre d\'eploy\'e au sein d'un unique domaine d'administration, dans lequel tous les noeuds/pairs sont suppos\'es coop\'eratifs
%=> pas de probl\'ematique de s\'ecurit\'e, confidentialit\'e, ...
%\item PosNet n'est pas pr\'vu pour les applications requ\'erant un support pour les noms de domaines hi\'erarchiques (une norme dans de nombreux syst\`emes de fichiers) ou de
%sch\'emas relationnels complexes (g\'er\'es par les bases de donn\'ees relationnelles)
%\item PosNet n'est pas pour les applications particuli\`erement sensibles \`a la latence 
%\end{itemize}
%
%\subsection{Approche adopt\'ee dans PosNet}
%
%\paragraph{Une architecture P2P semi-structur\'ee TODO}
%%Rationale de l'approche P2P structur\'ee/semi-structur\'ee : 
%Le paradigme P2P pour le passage \`a l'\'echelle, l'auto-organisation : 
%Le premier crit\`ere de passage \`a l'\'echelle d\'ecourage d'office le choix
%d'une solution centralis\'ee. En effet, un point central en plus de constituer
%un goulet d'\'etranglement et un \emph{single point of failure, }implique
%un \'etat en $O (N)$ (avec N le nombre de pairs)
%
%>>>Inserer tableau comparatif des solutions de gestion de donn\'ees d\'ecentralis\'ees
%
%% \begin{tabular}{}
%%   \hline
%%   & Mod\`ele de donn\'ees & Mod\`ele de requ\^\e tes & Traitements d\'ecentralis\'e ? & Echelle & Contraintes \\
%%   \hline
%%   Dynamo & 
%% \begin{itemize}
%% \item Tuple cl\'e-valeur  
%% \item Type de valeur : cha\^\i ne de caract\`eres
%% \item Multiples valeurs possible par cl\'e
%% \end{itemize} &
%% \begin{itemize}
%% \item put(), get(), delete()
%% \item Query ???
%% \end{itemize} &
%% Oui &
%% 10\^ 2 &
%% Commodity hardware infrastructure 
%% \\
%%   Solution & a & a & a & a & a \\
%%   \hline
%% \end{tabular}
%
%\begin{tabular}{|p{2cm}|p{3cm}|p{3cm}|p{3cm}}
% \hline
% Besoin & Technique & Avantages & D\'esavantages \\
% \hline
% D\'ecentralisation & Architecture P2P & Pas besoin d'infrastructure d\'edi\'ee comme dans Dynamo & Routage multihop => latence \\
% Routage guid\'e & Topologie semi-structur\'ee des pairs & Flexibilit\'e dans le placement des donn\'ees & Routage non optimal \\
% Traitement de requ\^etes comparatives & Structure de donn\'ees pr\'eservant information d'ordre partiel sur les donn\'ees & Localit\'e s\'emantique & El\'ements maximaux 
%constituent point de centralisation dans traitement des requ\^etes \\
% \hline
%\end{tabular}
%
%%http://www.sciencedirect.com/science?_ob=ArticleURL&_udi=B6VRG-4RTM36C-1&_user=870092&_rdoc=1&_fmt=&_orig=search&_sort=d&_docanchor=&view=c&_searchStrId=961296201&_rerunOrigin=google&_acct=C000046800&_version=1&_urlVersion=0&_userid=870092&md5=d5224aca592402620f96c905dcd66488
%
%\paragraph{Un organisation des donn\'ees selon un ordre partiel}
%
%<Pourquoi organiser les donn\'ees : inserer graphe axes expressivit\'e/optimalit\'e>
%

%>>>>>>>>>>>>>>>>
%

%

%
%\subsection{Conclusion TODO}
%Le d\'eveloppement de syst\`emes distribu\'es \`a l'\'echelle du Web a modifi\'e le paysage des solutions de stockage de donn\'ees. Le saut qualitatif dans le passage \`a l'\'echelle
%des applications met \`a mal l'h\'eg\'emonie du mod\`ele transactionnel traditionnel et induit un changement de paradigme dans la mani\`ere d'appr\'ehender la gestion de
%donn\'ees. Si les SGBD 
%demeurent la solution de choix par d\'efaut, lorsque le passage \`a l'\'echelle impose la partition et la distribution massive des donn\'ees, le choix d'un syst\`eme
%distribu\'e de donn\'ees totalement d\'ecentralis\'e s'impose face aux architecture trois-tiers classiques. 
%%Dans cette approche, les propri\'et\'es ACID et la s\'emantique SQL sont rel\^ach\'ees pour permettre une scalabilit\'e horizontale incr\'ementale.
%
%\begin{tabular}{|l|c|r|}
%  \hline
%  Symbole & Description \\
%  \hline
%  \hline
%  $\mathcal{O}$ & Ensemble des donn\'ees brutes \\
%  $\mathcal{S}$ & Espace des attributs \\
%  $g$ & Fonction de transformation des donn\'ees brutes en donn\'ees de l'index $g:\mathcal{O} \to\ \mathcal{S}$ \\
%  $d$ & Dimensionnalit\'e de l'espace des attributs \\
%  $n$ & Cardinalit\'e de l'ensemble image de $\mathcal{O}$ par $g$ \\
%  $N$ & Nombre de pairs \\
%  \hline
%\end{tabular}

% GOALS : http://lsirpeople.epfl.ch/punceva/project/accessp2p.htm
%     *  Investigate new access structures designed specifically for P2P information systems. The access structure should be self-organizing, without relying on centralized servers.
%     * All operations like insert, update and search should be based on local interactions only.
%     * Provide good scalability of resources spent by a single peer in the total amount of data in the network.
%     * Provide reliability even if certain numbers of peers are off-line.
%     * Solve the problem related to constructing the structure from scratch.
%     * Balancing the efforts among the peers.
%     * Support user's autonomy.

\subsection{Contexte}\label{subsec:Contexte}

Nous nous pla\c cons dans le contexte d'un environnement sans partage (de l'anglais << shared nothing >>), au sein duquel un ensemble de serveurs fournissent des services de stockage et de calcul
ind\'ependants. Les serveurs reposent sur une communication de point \`a point et ils forment un r\'eseau que l'on qualifie de sym\'etrique, c'est-\`a-dire d\'epourvu de serveur central ou de super-pair. 
Cet environnement est de plus suppos\'e volatile : un serveur peut joindre ou quitter le r\'eseau \`a tout moment. 
Ces caract\'eristiques sont pr\'esentent dans les r\'eseaux ad hoc, les r\'eseaux ambients et les r\'eseaux pair-\`a-pairs. 

%type d'applications : services en r\'eseau, gestion de donn\'es in situ, passage \`a l echelle incremental, pas d administration centralisee, etc. 

L'utilit\'e de ces services de stockage et de calcul est conditionn\'ee, entre autres, par leur capacit\'e \`a permettre l'extraction de donn\'ees. Nous retenons plus particuli\`erement deux crit\`eres pour caract\'eriser cette extraction : la compl\'etude et l'expressivit\'e. 
La compl\'etude garantit la localisation de l'ensemble des solutions pertinentes pour une requ\^ete. 
L'expressivit\'e signifie qu'il est possible d'effectuer des recherches par le contenu, au-del\`a des recherches traditionnelles par cl\'e ou mots cl\'es propos\'ees dans les DHT par exemple. 
Plus pr\'ecis\'ement, nous nous int\'eressons aux requ\^etes multidimensionnelles exactes (avec ou sans joker), aux requ\^etes par intervalles et enfin aux requ\^etes skyline (traditionnelles, sur un sous-espace, sous contraintes).  
% explciiter interet, demarche exploratoire, etc. 

Ces crit\`eres sont v\'erifi\'es par les m\'ethodes d'acc\`es traditionnelles, notamment en bases de donn\'ees spatiales. 
%+++
Toutefois, leur caract\`ere centralis\'e ne permet pas de les appliquer telles quelles dans notre contexte. 

\subsection{Objectifs et contraintes}\label{subsec:Objectifs et contraintes}

L'objectif de cette th\`ese est de concevoir un m\'ecanisme d'indexation distribu\'e permettant d'effectuer les op\'erations suivantes : 
insertion d'une donn\'ee, suppression d'une donn\'ee, recherche exacte, recherche par intervalles, recherche avec joker, recherche skyline. 
Notre solution PosNet permet de r\'epondre aux contraintes suivantes :
\begin{itemize}
\item L'ensemble des objets \`a indexer est repr\'esent\'e dans un espace d'attributs  
\item Les recherches portent sur le contenu (les valeurs d'attributs) et doivent porter sur l'ensemble des attributs simultan\'ement
\item Aucune information sur l'\'etat global du syst\`eme n'est accessible (absence d'annuaire central, de serveur central, d'<< oracle >>, etc.)
\item Les serveurs communiquent par le biais de messages point \`a point 
\item Un serveur peut se joindre au r\'eseau ou quitter le r\'eseau \`a tout moment (hors panne)
\end{itemize}

Ces hypoth\`eses fortes nous permettent de nous adresser \`a un large spectre de requ\^etes de contenu et d'environnements dynamiques et distribu\'es.
Ces hypoth\`eses requi\`erent notamment que les donn\'ees et les traitements soient r\'epartis sur l'ensemble des serveurs participants, sans utiliser un serveur central ou une architecture hi\'erarchique.

Parmi les solutions alternatives expos\'ees au chapitre \ref{chap:Indexation et localisation dans les syst\`emes distribu\'es \`a grande \'echelle}, 
l'approche bas\'ee sur des overlays P2P structur\'es/semi-structur\'es pour la conception d'index d\'ecentralis\'es couvre l'ensemble de ces hypoth\`eses.
Nous avons choisi cette approche pour Posnet. 

%\subsection{Probl\'ematique scientifique}\label{subsec:Probl\'ematique scientifique}
\subsection{Contributions}\label{subsec:Contributions}

Comme vu au chapitre \ref{chap:Indexation et localisation dans les syst\`emes distribu\'es \`a grande \'echelle}, les solutions d'index P2P qui supportent nativement 
les requ\^etes multidimensionnelles distribuent une structure de donn\'ees spatiale sur un ensemble des n\oe uds, formant alors un overlay. 
% +++
%Toutefois, aucune solution \`a notre connaissance ne permet un support natif simultan\'e des requ\^etes par intervalles et skyline. 

Les questions auxquelles nous r\'epondons dans cette th\`ese sont donc : Comment concevoir une structure de donn\'ees qui pr\'eserve
 une localit\'e offrant un support natif \`a la fois aux requ\^etes par intervalles et skyline ? Comment distribuer cette structure sur l'ensemble des pairs de l'overlay ? 
Comment l'exploiter et la maintenir de mani\`ere efficace et totalement d\'ecentralis\'ee ? Comment assurer la compl\'etude des recherches ? 

%\subsection{Contributions}\label{subsec:Contributions}

Dans cette th\`ese nous proposons un nouvel index multidimensionnel distribu\'e supportant nativement les requ\^etes par intervalles et skyline : PosNet. 

PosNet repose sur la cr\'eation d'une structure de donn\'ees multidimensionnelle de type graphe, permettant l'organisation les donn\'ees 
selon un \emph{ordre partiel} quelconque. 
Nous proposons une famille d'algorithmes exploitant les propri\'et\'es topologiques de ce graphe. Ces algorithmes permettent entre autres la recherche de points et d'intervalles. De plus, le choix de l'\emph{ordre de Pareto} (ou ordre produit) permet de r\'epondre naturellement aux requ\^etes de front de Pareto. 
Nous montrons qu'il est possible de d\'eployer, maintenir et exploiter ces algorithmes de mani\`ere totalement d\'ecentralis\'ee, ce qui rend notre solution adaptable \`a un environnement sans partage.   

Nous d\'etaillons nos contributions ci-dessous :  

% \subsubsection{Utilisation d'un ordre partiel}
% MINI ETAT ART ORDRE PARTIEL
% Applications connues de la notion d'ordre partiel dans la gestion de donn\'ees : 
% \begin{itemize}
% \item A la recherche de graphes [A self-organizing retrieval system for
% graphs, Robert Levinson, , AAAI-84 Proceedings, 1984]. Les graphes d'un
% syst\`eme quelconque sont consid\'er\'es comme des sous-graphes d'un graphe
% universel. On g\'en\'eralise la notion de sous-graphe \`a celle de
% ``concept``. Relation d'ordre partielle utilis\'ee : "sous-graphe de".
% 
% \item Bases multidimensionnelles OLAP. [An efficient, robust method for
% processing of partial top-k/bottom-k queries using the RD-Tree in OLAP] =>
% partial top-k/bottom-k queries
% 
% \item Allocateur de ressources bas\'e agents dans les grilles [Using mobile
% agents for resource sharing, Alexandru Suna et al]. Les agents organisent
% leurs connaissances des ressources en un treillis de gallois pour effectuer
% leurs d\'ecisions de migration de code. La relation d'ordre utilis\'ees est
% ""
% 
% \item http://ethesis.helsinki.fi/julkaisut/mat/tieto/vk/tarkoma/
% 
% \item http://www.inf.unisi.ch/carzaniga/papers/cucs-902-00.pdf
% \end{itemize}

%En reprenant point par point les probl\'ematiques \'enonc\'ees, les contributions de cette th\`ese sont : 
% Selon l'\'etat de l'art \'etabli au pr\'ec\'edent chapitre, il n'existe \`a notre connaissance aucune solution satisfaisant actuellement l'ensemble des objectifs vis\'es.
% D'o\`u notre proposition : \emph{PosNet, un nouvel overlay P2P s\'emantique semi-structur\'e, bas\'e sur une structure de donn\'ees originale appel\'ee <<pograph>>}. 
% Le d\'etail des contributions apport\'ees par PosNet : 
%PosNet un nouvel index P2P s\'emantique semi-structur\'e fond\'e sur une structure de donn\'ees originale d\'esign\'ee par "pograph" :

\paragraph {\textbf{~~~Contribution 1 : Le pograph, une structure de donn\'ees originale}} 
\textit{\'Elaboration d'une nouvelle structure de donn\'ees de type graphe, d\'enomm\'ee << pograph >>, bas\'ee sur un ordre partiel d\'efini sur l'ensemble des donn\'ees.}
\vspace{0.6cm}

% \subsubsection{Conception d'une structure de donn\'ees}
% La premi\`ere contribution de cette th\`ese est donc la proposition d'une nouvelle structure de donn\'ees ad hoc de type graphe, 
% bas\'ee sur un ordre partiel d\'efini 
% sur l'ensemble des donn\'ees (repr\'esent\'ees sous forme de vecteurs d'attributs), et dont les avantages sont de : 
Les avantages du pograph sur les structures de donn\'ees employ\'ees par d'autres overlays P2P sont multiples : 
\begin{itemize}
\item Cette structure permet l'indexation native des donn\'ees multidimensionnelles, m\^eme avec des valeurs manquantes ; 
\item L'ordre partiel d\'efini sur l'ensemble des donn\'ees permet de structurer l'espace de description et par cons\'equent,
  \begin{itemize}
  \item De pr\'eserver une localit\'e spatiale, et donc d'optimiser les requ\^etes par intervalles, 
  \item D'optimiser les requ\^etes de front de Pareto (skyline et ses variantes) gr\^ace \`a l'expression d'un ordre de Pareto, 
  \item De garantir la compl\'etude de la recherche,     
  \item De g\`erer les requ\^etes partielles.  
  \end{itemize}
\end{itemize}
\vspace{0.6cm}

L'exploitation du pograph dans un environnement sans partage soul\`eve deux d\'efis : (i) son parcours distribu\'e ; 
(ii) le maintient de sa structure dans un environnement dynamique. Ils font l'objet des deux contributions d\'etaill\'ees repsectivement
dans les chapitres \ref{chap:Plan de transfert des requ\^etes} et \ref{chap:Plan de contr\^ole} :
%, sous la forme de \emph{protocoles de routage distribu\'es concurrents asynchrones}. 

%\paragraph {\textbf{~~~Contribution 2 : Conception de protocoles de routage parall\`eles distribu\'es concurrents asynchrones}}
%\paragraph {\textbf{~~~Contribution 2 : Conception de r\`egles de routage dans le pograph distribu \'e : routage sans vall\'ee}}
\paragraph {\textbf{~~~Contribution 2 : Algorithmes de parcours dans un pograph : les chemins sans vall\'ee}}    
\textit{Elaboration d'algorithmes de recherche dans un pograph selon des chemins appel\'es chemins sans vall\'ee, inspir\'es d'un mod\`ele issu des r\'eseaux TCP/IP. Elaboration d'un protocole de routage des requ\^etes pour les recherches dans un pograph distribu\'e.}
%\textit{Elaboration de r\`egles pour le routage des requ\^etes de recherche dans un overlay P2P dont la topologie est inf\'er\'ee d'un pograph. Ces r\`egles reposent sur des parcours de graphe inspir\'ees d'un mod\`ele issu des r\'eseaux TCP/IP.} 
\vspace{0.6cm}

%\`A chaque type de requ\^ete correspond un algorithme de parcours dans le pograph. Le pograph \'etant distribu\'e sur un ensemble de 
%n\oe uds, les chemins peuvent traverser plusieurs pairs. Un protocole de routage est donc \'elabor\'e, afin 
%d'assurer l'acheminement des requ\^etes d'un pair \`a un autre, sur le chemin sans vall\'ee.  

Un protocole de recherche bas\'e sur des chemins sans vall\'ee permet, gr\^ace \`a un nombre r\'eduit de r\`egles, de :  
\begin{itemize}
\item S\'electionner une route dans l'overlay sur la base d'informations locales uniquement ;
\item S\'electionner une route dans l'overlay \`a partir d'un pair quelconque de l'overlay ;
\item Rechercher simultan\'ement sur l'ensemble des attributs ;
\item Elaguer l'espace de recherche ;
\item Garantir la compl\'etude de la recherche. 
%\item Couvrent les types de requ\^etes d\'ecrits ci-avant
\end{itemize}
%\vspace{0.6cm}
On d\'esigne l'ensemble de ces protocoles sous le terme de \emph{plan de requ\^etes} de PosNet. 

\paragraph {\textbf{~~~Contribution 3 : M\'ecanismes d'auto-stabilisation pour la gestion automatique du nombre de n\oe uds ou de donn\'ees participant \`a l'overlay}} 
\textit{\'Elaboration de m\'ecanismes de partition (ou de r\'eunion) des n\oe uds et de placement (ou de suppression) des donn\'ees sur les n\oe uds. % : insertion, suppression, partition d'un n\oe ud.
}
\vspace{0.6cm}

Sur la base de connaissances locales uniquement, ces protocoles permettent :  
\begin{itemize}
\item L'insertion et la suppression de donn\'ees \`a la vol\'ee ;
\item La gestion de l'arriv\'ee ou du d\'epart d'un pair, en redistribuant dynamiquement l'ensemble des donn\'ees ;
\item La pr\'eservation de la continuit\'e du service de recherche durant des modifications auxquelles est soumis l'overlay.
%\item La pr\'eservation des propri\'et\'es de routage de l'overlays
\end{itemize}
%\vspace{0.6cm}
On d\'esigne l'ensemble de ces protocoles sous le terme de \emph{plan de contr\^ole} de PosNet. 

% \subsubsection{Impl\'ementation}
% La troisi\`eme contribution de cette th\`ese est une impl\'ementation distribu\'ee de PosNet en Python, Pyposnet, disponible sur google code.
\paragraph {\textbf{~~~Contribution 4 : Pyposnet, un prototype de PosNet}} 
\textit{Pyposnet est une impl\'ementation distribu\'ee en Python du plan de requ\^etes et du plan de contr\^ole de PosNet, nomm\'ee Pyposnet et disponible sur google code \cite{pyposnet}.}
\vspace{0.6cm}
%SLOT EVALUATION

%La suite du document d\'ecrit le pograph (chapitre ???) et la mani\`ere dont on a lev\'e ce verrou dans PosNet : [reste du PLAN].

%Les dimensions h\'et\'erog\`enes sont g\'er\'ees dans PosNet, en rempla\^iant simplement l'attribut manquant par l'\'el\'ement minimal $\bot$. [TODO \`a r\'ediger]



%
%  Les objectifs sont poursuivis dans le cadre des hypoth\`eses suivantes : 
% \paragraph{Hypoth\`eses de travail}
% \begin{itemize}
% \item L'overlay repose sur une infrastructure de communication pr\'e-existante
% \item L'index est d\'ploy\'e dans un domaine d'administration unique, au sein duquel tous les noeuds sont suppos\'es de confiance
% \item Mod\`ele de donn\'ees : Les donn\'ees sont mod\'elisables par des vecteurs d'attributs ; les attributs sont ind\'ependants ; 
% une relation d'ordre totale est d\'efinie sur chaque domaine de d\'efinition des attributs
%\item NO stringent latency requirements => queries CAN be routed through multiple nodes (and tolerate variability in response time)
%\end{itemize}
% 
% Dans le cadre de ces hypoth\`eses, les objectifs principaux de PosNet sont les suivants : TODO reprendre crit\`eres de l'\'etat de l'art 
% \paragraph{Besoins fonctionnels :} 
% \begin{itemize}
% \item Support natif de donn\'ees multi-dimensionnelles 
% \item Support natif de requ\^etes par intervalles et de comparaison
% \item Support natif de requ\^etes skyline
% \end{itemize}

% \paragraph{Besoins non fonctionnels :}
% \begin{itemize}
% \item Passage \`a l'\'echelle incr\'emental et syst\`eme auto-organisant => d\'ecentralisation (prise de d\'ecision uniquement sur la base d'informations locales)
% \item Efficacit\'e et compl\'etude des recherches => recherche guid\'ee. Pas de protocoles par inondation ; pas de recherche exhaustive ; 
% pas de d\'ecomposition des requ\^etes complexes en requ\^etes plus simples
% \item progressiveness
% \end{itemize}
% \item D\'ecentralisation => prise de d\'ecision uniquement sur la base d'informations locales
% \item Syst\`eme auto-organisant : r\^oles sym\'etriques des n\oe uds ; passage \`a l'\'echelle incr\'emental %=> pas de SGBD, pas de sharding, pas de client/serveur, ... 
% \end{itemize}
% \vspace{0.6cm}

% \subsection{Approche choisie} \label{subsec:Approche choisie}
% L'\'etat de l'art r\'ealis\'e au chapitre pr\'ec\'edent 
% souligne l'absence de solution satisfaisant l'ensemble des besoins exprim\'es ci-dessus. 
% Dans la recherche d'un nouveau mod\`ele d'index, il nous conduit par-ailleurs \`a opter pour l'utilisation 
% d'un \emph{overlay P2P s\'emantique semi-structur\'e}. 
%Ce choix est justifi\'e par la correspondance suivante entre besoins et choix technologiques : TODO reprendre les solutions qui ne conviennent pas selon discussions \'etat de l'art

%La table \ref{}
%La table \ref{TableauYo}% r\'ecapitulatif des diff\'erentes techniques mise en \oe uvre dans PosNet.}  
La table \ref{Tableaurecapitulatif}
r\'ecapitule les diff\'erents choix techniques faits dans PosNet et leurs avantages respectifs (par-rapport \`a d'autres techniques) : 
\vspace{0.6cm}

\begin{table} [h!]
\begin{tabular}{|c|c|c|}
\hline
Besoin & Technique & Avantage \\
\hline
\hline
% D\'ecentralisation (architecture & Overlay P2P & Passage \`a l'\'echelle \\
% sym\'etrique supportant) &  & incr\'emental, \\
%  la parall\'elisation) &  & Auto-organisation \\
% \hline
 &  & Robustesse car architecture \\
D\'ecentralisation & Overlay P2P & sym\'etrique ; efficacit\'e car \\
 &  & parall\'elisation des traitements ; \\
&  & auto-organisation \\
\hline
 &  & Robustesse et possibilit\'e\\
Efficacit\'e et compl\'etude  & Overlay P2P & de r\'epartition de charge \\
des recherches  &    semi-structur\'e  &  gr\^ace \`a la flexibilit\'e  \\
&  & dans le placement des donn\'ees \\
\hline
 &  & Pas de pr\'e-traitements type   \\
Support de donn\'ees & Structure de donn\'ees & r\'eduction de la dimensionalit\'e \\
multi-dimensionnelles & multi-dimensionnelle & des donn\'ees ni de \\
&  & d\'ecomposition des requ\^etes \\
 %&  & ; pr\'eservation de la localit\'e \\
\hline
Support de requ\^etes & Placement des donn\'ees & Plus flexible que \\
 par intervalles & pr\'eservant une localit\'e & l'indexation d'intervalles \\
&  &  \\
\hline
Support de requ\^etes & Structure de donn\'ees & Optimisation  \\
skyline & pr\'eservant un &  des requ\^etes skyline\\
  &  ordre de Pareto &  \\
\hline
\end{tabular}
\caption{Tableau r\'ecapitulatif des diff\'erents choix techniques effectu\'es dans PosNet}
 \label{Tableaurecapitulatif}
\end{table}

\paragraph{} 
Remarques : 
\begin{itemize}
\item PosNet est pr\'evu pour un d\'eploiement au sein d'un unique domaine d'administration, dans lequel tous les n\oe uds sont suppos\'es coop\'eratifs 
(pas de probl\'ematique de s\'ecurit\'e, confidentialit\'e, etc.)
\item PosNet n'est pas pr\'evu pour les applications requ\'erant un support pour les noms de domaines hi\'erarchiques (une norme dans de nombreux syst\`emes de fichiers) ou de
sch\'emas relationnels complexes (g\'er\'es par les bases de donn\'ees relationnelles)
\item PosNet n'est pas indiqu\'e pour les applications particuli\`erement sensibles \`a la latence. Le routage P2P \'etant multi-sauts et la taille des routes dans PosNet \'etant variable, 
les d\'elais ne sont pas d\'eterministes.  
\end{itemize}

\section{Pr\'esentation g\'en\'erale de PosNet} \label{sec:Pr\'esentation g\'en\'erale de PosNet}

Nous pr\'esentons ici notre solution PosNet. Nous introduisons en particulier la structure de donn\'ees sur laquelle PosNet repose, le pograph. 

Nous avons vu pr\'ec\'edemment en \ref{subsec:Conception g\'en\'erique d'un overlay P2P} que la conception d'un overlay se ram\`ene \`a une s\'erie de relations : 

\begin{itemize}
\item $g : \mathcal{O} \rightarrow \mathcal{S}$ : Choix d'une repr\'esentation des donn\'ees ;
\item $f\footnote{Le choix de $f$ n'ayant pas d'incidence dans notre solution, nous ne revenons pas dessus dans la suite du document. Ce peut \^etre par exemple l'adresse IP et le num\'ero de port du serveur.} : \mathcal{N} \rightarrow \mathcal{V}$ : Choix d'un espace de nommage des n\oe uds ; 
\item $p : g\left\langle \mathcal{O} \right\rangle \rightarrow f\left\langle \mathcal{N} \right\rangle$ : Choix d'une strat\'egie de placement des donn\'ees. 
% Une strat\'egie de placement distribue l'ensemble des donn\'ees (images de $\mathcal{O}$ par $g$) sur l'ensemble des n\oe uds (images de $\mathcal{N}$ par $f$). 
% Elle supporte l'ajout ou la suppression d'objets de $\mathcal{O}$, ainsi que l'arriv\'ee ou le d\'epart de n\oe uds dans $\mathcal{N}$ ;
\item $r : f\left\langle \mathcal{N} \right\rangle \times f\left\langle \mathcal{N} \right\rangle \rightarrow \mathcal{R}$ : Choix d'une strat\'egie de routage 
% ($\mathcal{R}$ : ensemble des routes). Il doit y avoir une route entre toute paire de n\oe uds de $\mathcal{V}$.
\end{itemize}
\vspace{0.6cm}

%De haut en bas : \\
%Dans ce qui suit, chaque couche est d\'ecrite (de haut en bas). \\

Dans ce qui suit, nous donnons pour PosNet les relations $g$ et $p$ dans l'architecture d'indexation en \ref{subsec:Architecture d'indexation}, et la strat\'egie de routage $r$ dans l'architecture de localisation en \ref{subsec:Architecture de localisation}.  
%$r : g\left\langle \mathcal{V}   dans l'architecture de localisation (\ref{subsec:Architecture de localisation})

%(i) le mod\`ele de donn\'ees, (ii) la structure de donn\'ees pograph et la mani\`ere dont elle d\'etermine la structure de l'overlay PosNet et (iii) les chemins sans vall\'ee dans le pograph et les routes qui en d\'ecoulent dans l'overlay.

\subsection{Architecture d'indexation}\label{subsec:Architecture d'indexation}

%Si nous reprenons la figure \ref{fig:couchesboitenoireindexationexpandtotal} le sch\'ema du 
%chapitre \ref{chap:Indexation et localisation dans les syst\`emes distribu\'es \`a grande \'echelle} et en d\'etaillant la
%<< bo\^ite noire >> repr\'esentant l'index distribu\'e : 
Nous illustrons la r\'ealisation dans PosNet des \'etapes $g$ et $p$ en reprenant sur la figure \ref{fig:couchesboitenoireindexationexpandtotal}
la repr\'esentation abstraite d'un index distribu\'e \'etudi\'ee dans le 
chapitre \ref{chap:Indexation et localisation dans les syst\`emes distribu\'es \`a grande \'echelle} : 

\begin{figure}[!h]
\begin{center}
\epsfig{file=fig/CouchesBoiteNoireIndexationExpandTotal,scale=0.6}
\caption{TODO reprendre les notations + repenser fleche car on dirait transformation /// Couches fonctionnelles d'indexation et de localisation utilis\'ees dans PosNet}
\label{fig:couchesboitenoireindexationexpandtotal}
\end{center}
\end{figure}

Entre l'espace des objets $g\left\langle \mathcal{O}\right\rangle$ et la couche r\'eseau $\mathcal{N}$, 
%pr\'esent\'es aux sections \ref{sec:Mod\`ele de donn\'ees utilis\'e} \ref{subsec:Conception g\'en\'erique d'un overlay P2P}. 
s'intercalent dans PosNet trois couches fonctionnelles. De haut en bas sur la figure \ref{fig:couchesboitenoireindexationexpandtotal} : l'\'etape $g$ correspond dans PosNet au passage de l'ensemble des 
objets \`a l'espace des attributs et l'\'etape $p$ au passage de l'espace des attributs au pograph, puis du pograph \`a sa partition et \`a sa distribution 
sur l'overlay (\'etape de placement des donn\'ees). Nous d\'etaillons maintenant chaque couche fonctionnelle (de haut en bas). 


%Le chapitre \ref{chap:Indexation et localisation dans les syst\`emes distribu\'es \`a grande \'echelle} a fournit une 
%repr\'esentation abstraite d'un index distribu\'e. Nous en d\'ecrivons ici la r\'ealisation par PosNet. 
%
%On retrouve \`a la figure \ref{fig:couchesboitenoireindexationexpandtotal}
%l'espace des objets $\mathcal{O}$ et la couche r\'eseau $\mathcal{N}$. 
%%pr\'esent\'es aux sections \ref{sec:Mod\`ele de donn\'ees utilis\'e} \ref{subsec:Conception g\'en\'erique d'un overlay P2P}. 
%La nouveaut\'e se situe \`a droite du sch\'ema, avec les trois couches fonctionnelles de notre index. De haut en bas : \\
%%Dans ce qui suit, chaque couche est d\'ecrite (de haut en bas). \\
%\begin{figure}[!h]
%\begin{center}
%\epsfig{file=fig/CouchesBoiteNoireIndexationExpandTotal,scale=0.6}
%
%\caption{TODO reprendre les notations /// Architecture de PosNet: les diff\'erentes couches fonctionnelles.}
%\end{center}
%\label{fig:couchesboitenoireindexationexpandtotal}
%\end{figure}
\paragraph{Espace des attributs $\mathcal{S}$.} %La premi\`ere couche est constitu\'ee de l'\emph{espace des attributs} $\mathcal{S}$. %$\mathcal{S}$ joue le r\^ole d'espace de repr\'esentation des objets.
%Le mod\`ele de donn\'ee de PosNet est celui d\'efini dans la section \ref{sec:Mod\`ele de donn\'ees utilis\'e}. 
La section \ref{sec:Mod\`ele de donn\'ees utilis\'e} a introduit le mod\`ele de donn\'ees utilis\'e dans PosNet. Nous le compl\'etons ici. 

%Une donn\'ee dans $\mathcal{S}$ est repr\'esent\'ee par un vecteur dans l'espace form\'e par le produit cart\'esien des . 
% Par exemple, soit $\mathcal{S}=\mathbb{R}^{\textrm{d}}$. Une solution $p$ de l'espace $S$ est alors d\'efinie par $d$ attributs, chacun \`a valeur dans $\mathbb{R}$. 
% On note : $p = \{ p[1], \ldots,\ p[d]\}$, o\`u $p[j] = s_j(o_i)$. 
% \begin{figure}[!h]
% \begin{center}
% \epsfig{file=fig/ex_solution,scale=0.4}
% \label{fig:exsolution}
% %\caption{TODO modifier graphe semantique //// Exemple d'espace des solutions avec trois dimensions : ${S=\mathbb{R^{\textrm{3}}}}$, $s=(d_{1},d_{2},d_{3})$}
% \caption{TODO reprendre les notations //// Exemple de repr\'esentation d'un objet $o$ comme un point $p$ dans un espace des attributs \`a trois dimensions : 
% $p = \{ s_1(o), s_2(o), s_3(o)\}$}
% \end{center}
% \end{figure}
%Par exemple, une solution $s=(s_{1},s_{2},\ldots,s_{d})$ d\'efinie sur $d$ attributs \`a valeur dans $\mathbb{R}$ est elle repr\'esent\'ee par un point de l'espace 
%$\mathcal{S=\mathbb{R^{\textrm{d}}}}$. 
%Par exemple, si tous les attributs d'un objet ont $\mathbb{R}$ comme domaine, une solution sera un point de l'espace $\mathcal{S=\mathbb{R^{\textrm{d}}}}$ 
Un espace de solutions $\mathcal{S}_{\mathcal{O}}$ pour un ensemble des objets $\mathcal{O}$ est un ensemble de tuples $\left( s_1,\ldots,s_d \right)$ tel que : 
\begin{enumerate}
\item Pour un tuple, chaque attribut $s_i$, $1\leq i \leq d$, correspond \`a une dimension $d_i$ ;
%Chaque point de $\mathcal{S}_{\mathcal{O}}$ est un vecteur de taille $d$ ;
\item On note $V_i$ l'ensemble des valeurs possibles pour l'attribut $s_i$. Pour chaque composante $i$ on introduit une valeur suppl\'ementaire $\bot_i$ qui indique une valeur manquante. 
On note $V^{*}_i=V_i\cup \{\bot_i\}$ l'ensemble des valeurs possibles pour la $i$-\`eme dimension ;
%\item Chaque valeur $v_i$ d'un attribut $a_i$ est un \'el\'ement de l'ensemble $V_{a_i} \cup \{\bot,* \}$ des valeurs possibles pour l'attribut $a_i$ (les symboles $\bot$ et $*$ sont 
%expliqu\'es plus bas, Section \ref{subsec:graphesemantique}) ;
\item On munit chaque $V^{*}_i$, $1\leq i \leq d$, d'un ordre total $\leq_{i}$. 
\end{enumerate}
Le symbole sp\'ecial $\bot$ permet de g\'erer l'h\'et\'erog\'en\'eit\'e dans la dimension des objets de l'espace d'origine. 

L'acquisition des attributs caract\'erisant les objets est en-dehors du champ de ce travail : nous supposons qu'il est d\'eduit de $\mathcal{O}$ par un expert du domaine. 

\paragraph{Pograph.} La deuxi\`eme couche est un raffinement de l'espace des solutions. En effet, on ordonne les solutions selon une relation d'ordre partiel au sein d'une structure de graphe appel\'ee 
\emph{pograph}. Le pograph offre une vue globale des donn\'ees index\'ees. Les algorithmes de recherche d\'evelopp\'es dans PosNet (cf. 
chapitre \ref{chap:Plan de transfert des requ\^etes}) reposent sur les propri\'et\'es topologiques de ce graphe, que l'on d\'etaille un peu plus loin, en \ref{subsec:Pograph}. 

La relation d'ordre partiel sp\'ecifique que nous avons choisie d'impl\'ementer est la relation d'ordre produit, ou ordre de Pareto.  
Cela dit, il est essentiel de souligner que la relation d'ordre a vocation d'\^etre adapt\'ee, afin de refl\'eter les besoins applicatifs. D'autres exemples de relation sont discut\'es dans les perspectives, chapitre \ref{chap:Conclusion et Perspectives}. 

\paragraph{Placement des donn\'ees} La troisi\`eme couche est une projection du pograph sur un sous-ensemble des serveurs. 
Le pograph est partitionn\'e en sous-graphes et chaque sous-graphe affect\'e \`a un serveur. 
Les serveurs dot\'es d'un sous-graphe participent au traitement des requ\^etes et forment le r\'eseau overlay. 
On les nommera pairs ou n\oe uds dans la suite du document. Il y a donc une bijection entre la partition du pograph et l'ensemble des pairs. 

%En d'autres termes, s'il existe deux noeuds s\'emantiques, un dans chaque partition, reli\'es par un arc. [TODO sch\'ema] 
Chaque pair supervise les donn\'ees figurant dans son sous-graphe du pograph. 
Pour chaque donn\'ee supervis\'ee, un pair maintient une liste d'\'elements dans $\mathcal{V}$ rep\'esentant les serveurs 
h\'ebergeant la donn\'ee en question. La valeur de retour d'une requ\^ete est une liste d'\'el\'ements de $f\left\langle \mathcal{N} \right\rangle$. 

Deux pairs dans l'overlay se connaissent si 
et seulement si leurs sous-graphes sont connect\'es dans le pograph. Si le voisinage d'un pair dans PosNet est enti\`erement
d\'etermin\'e par les connexions de son sous-graphe avec les autres sous-graphes, la libert\'e dans le choix de la partition se
traduit en libert\'e dans le choix du voisinage. C'est pourquoi PosNet se classe dans les \emph{overlays semi-structur\'e} (cf. section \ref{sec:Mod\`eles d'index} du chapitre pr\'ec\'edent). 

Notons enfin que chaque pair poss\`ede une connaissance partielle de son environnement : connaissance partielle des objets index\'es ; connaissance partielle des autres pairs composant le r\'eseau overlay
%\footnote{Le cas particulier o\`u le pograph serait partitionn\'e de telle sorte \`a ce que tout les pairs se connaissent 
%(topologie de voisinage en graphe complet) est discut\'e chapitre "Plan de Contr\^ole".}.

%[A SA PLACE ?]Concernant la relation d'ordre partiel utilis\'ee pour construire le pograph, on a fait ici le choix de l'ordre produit (cf. \ref{subsec:graphesemantique}). 
%Le choix de cette relation d'ordre courante se justifie pour plusieurs raisons. Tout d'abord par sa simplicit\'e et sa g\'en\'eralit\'e : tous les attributs sont consid\'er\'es 
%ind\'ependants et 
%d'\'egale importance. Ensuite, par sa pertinence au regard de notre mod\`ele de requ\^etes : l'organisation des solutions en fonction de leur dominance permet d'instorer une localit\'e 
%s\'emantique riche, au-del\`a d'un ordre purement num\'erique ou aphab\'etique. On esp\`ere ainsi gagner en efficacit\'e pour les requ\^etes par intervalle, mais surtout pour les 
%requ\^etes comparatives. 

\subsection{Architecture de localisation} \label{subsec:Architecture de localisation}

La fonctionnalit\'e de localisation peut \^etre d\'ecrite comme une s\'erie de correspondances entre la couche du pograph et la couche physique. 
%Deux pairs dans l'overlay se connaissent si 
%et seulement si leurs sous-graphes sont connect\'es dans le pograph. Si le voisinage d'un pair dans PosNet est enti\`erement
%d\'etermin\'e par les connexions de son sous-graphe avec les autres sous-graphes, la libert\'e dans le choix de la partition se
%traduit en libert\'e dans le choix du voisinage. C'est pourquoi PosNet se classe dans les \emph{overlays semi-structur\'e} (cf. section \ref{sec:Mod\`eles d'index} du chapitre pr\'ec\'edent). 

Lorsqu'une requ\^ete est inject\'ee dans le syst\`eme, elle est achemin\'ee de pair en pair dans le r\'eseau \emph{overlay} jusqu'\`a avoir visit\'e l'ensemble des pairs couvrant des donn\'ees pertinentes.
La figure \ref{fig:Architecturelocalisation} simule un parcours de recherche. La partition du pograph est signal\'ee par des pointill\'es. \`A chaque sous-graphe correspond un pair. 
Les ronds rouges, reli\'es par des traits rouges, repr\'esentent les noeuds du pograph parcourus lors du traitement de la requ\^ete.
Les bo\^ites rouges repr\'esentent les pairs travers\'es par la requ\^ete. Les traits rouges entre les bo\^ites rouges ou bleues composent la route de la requ\^ete dans le r\'eseau physique. 

\begin{figure}[!h]
\begin{center}
\epsfig{file=fig/CouchesBoiteNoireLocalisationExpand3,scale=0.6}
%\end{center}
\caption{TODO remplacement couleur par motif ?\\\ Architecture de localisation de PosNet : exemple de chemin dans l'overlay et sa transposition dans le r\'eseau physique}
\label{fig:Architecturelocalisation}
\end{center}
\end{figure} 

\`A la r\'eception d'une requ\^ete, un pair utilise son sous-graphe du pograph pour (i) en extraire les donn\'ees satisfaisant la requ\^ete ; (ii) d\'eterminer le cas \'ech\'eant les pairs adjacents auxquels retransmettre la requ\^ete. 

\`A chaque type de requ\^ete correspond un algorithme de recherche dans le pograph. 
N\'eanmoins, tous les algorithmes ont en commun de ne calculer que des chemins \og sans vall\'ee \fg{}. Comme expos\'e dans ce qui suit
 (\ref{subsubsec:Chemins sans vall\'ee dans le pograph}), cette sp\'ecificit\'e des chemins dans le pograph est la r\'esultante des propri\'et\'es structurelles du graphe et permet l'optimisation des recherches dans PosNet.    
 
\subsection{Pograph} \label{subsec:Pograph}

%Nous avons vu dans la section \ref{subsec:Conception g\'en\'erique d'un overlay P2P} que la conception d'un overlay g\'en\'erique peut \^etre ram\`en\'ee \`a une s\'erie d'associations : 
%
%\begin{itemize}
%\item $g : \mathcal{O} \rightarrow \mathcal{S}$ : Choix d'une repr\'esentation des donn\'ees ;
%\item $f : \mathcal{N} \rightarrow \mathcal{V}$ : Choix d'un espace de nommage des n\oe uds ; 
%\item $p : g\left\langle \mathcal{S} \right\rangle \rightarrow g\left\langle \mathcal{V} \right\rangle$ : Choix d'une strat\'egie de placement des donn\'ees. 
%% Une strat\'egie de placement distribue l'ensemble des donn\'ees (images de $\mathcal{O}$ par $g$) sur l'ensemble des n\oe uds (images de $\mathcal{N}$ par $f$). 
%% Elle supporte l'ajout ou la suppression d'objets de $\mathcal{O}$, ainsi que l'arriv\'ee ou le d\'epart de n\oe uds dans $\mathcal{N}$ ;
%\item $r : g\left\langle \mathcal{V} \right\rangle \times g\left\langle \mathcal{V} \right\rangle \rightarrow \mathcal{R}$ : Choix d'une strat\'egie de routage 
%% ($\mathcal{R}$ : ensemble des routes). Il doit y avoir une route entre toute paire de n\oe uds de $\mathcal{V}$.
%\end{itemize}
%\vspace{0.6cm}
 
%   \begin{enumerate}
%     \item D\'efinition d'un espace d'indexation $\mathcal{I}$. Parmi les
%     facteurs \`a prendre en compte : passage \`a l'\'echelle ($card (
%     \mathcal{I})$ en $O (k^d)$, pour $k \geq 2$ et $d \in \mathbb{N}$ tr\`es
%     grand => $\mathcal{I}$ croit de mani\`ere exponentielle pour un $k$
%     fix\'e), ind\'ependence par rapport \`a la localisation g\'eographique.
%     L'espace $\mathcal{I}$ est suppos\'e dot\'e d'une fonction distance
%     not\'ee $\triangle$ ($\mathcal{I}$ espace m\'etrique ou pseudo-m\'etrique)
%     
%     \item D\'efinition d'un partitionnement des donn\'ees/de la structure de
%     donn\'ees, afin de r\'epartir sur les noeuds la responsabilit\'e de
%     l'espace de donn\'ees,
%     
%     \item D\'efinition d'une topologie logique des noeuds => r\'eseau overlay
%     ou graphe de noeuds qui connectent les noeuds et leur permet de coop\'erer
%     pour retrouver n'importe quelle donn\'ee de l'espace des donn\'ees
%     (\emph{reachability}).
%     
%     \item D\'efinition des protocoles de routage. La notion de routage
%     comprend i) la constitution d'un voisinage (construction et maintenance
%     automatiques des tables de routage) ; ii) la s\'election des routes (le
%     choix du prochain voisins \`a visiter).
%   \end{enumerate}

%TODO : mapper ces 4 \'etapes sur ce qui suit. 

Nous d\'efinissons ici le pograph et les concepts fondamentaux qui lui sont associ\'es : ordre partiel et chemins sans vall\'ee.  

%(i) la structure d'acc\`es distribu\'ee ou pograph et (ii) les algorithmes de parcours du pograph ou chemins sans vall\'ee. 

%\subsubsection{Structure d'acc\`es distribu\'ee : le pograph}\label{subsec:graphesemantique}
%[TODO transition ?]
\subsubsection{Ordre partiel d\'efinit sur l'ensemble des donn\'ees}

Afin d'assurer un m\'ecanisme de comparaison valable sur l'ensemble des ressources, PosNet requiert que l'ensemble des donn\'ees de $S$ soit muni d'un ordre partiel. On rappelle ici 
les \'el\'ements de math\'ematiques n\'ecessaires \`a la compr\'ehension du mod\`ele. 
%Le lecteur au fait de ces d\'efinitions peut se reporter directement en \ref{susubsec:graphesemantique}.

\begin{definition}
Une \textbf{relation d'ordre} $\preceq$ sur un ensemble $E$ est une relation binaire sur $E$ r\'eflexive, transitive et antisym\'etrique : 
\begin{itemize}
\item [{\textit{~R\'eflexive~}:}] Si elle met tout \'el\'ement en relation avec lui-m\^eme, c'est-\`a-dire si : $\forall x\in E,x\preceq x$
%\begin{itemize}
%\item [{$\forall x\in E,x\Re x$}]~
%\end{lyxlist}
\item [{\textit{~Antisym\'etrique}~:}] Si les \'el\'ements distincts ne sont jamais en relation mutuelle, c'est-\`a-dire si :
 $\forall x\in E,\forall y\in E,[(x\preceq y)\wedge(y\preceq x)]\Rightarrow[x=y]$
\item [{\textit{~Transitive}\textit{~}:}] Si deux \'el\'ements sont mis en relation d\`es qu'on peut transiter par un troisi\`eme, c'est-\`a-dire
si : $\forall x\in E,\forall y\in E,\forall z\in E,[(x\preceq y)\wedge(y\preceq z)]\Rightarrow[x\preceq z]$
\end{itemize}
\end{definition}
\begin{definition}
Une relation d'ordre est dite \textbf{partielle} s'il existe deux \'el\'ements que l'on ne peut pas mettre en relation, ni dans un sens ni dans
l'autre.\\
$$\exists x\in E,\exists y\in E,[(x\npreceq y)\wedge(y\npreceq x)]$$
$x$ et $y$ sont alors incomparables, ce que l'on note : $x\parallel y$.
\end{definition}
Muni d'un ordre partiel, l'ensemble $E$ est dit \emph{partiellement ordonn\'e} ou poset (pour << Partially Ordered SET >>).\\ 
L'ordre partiel choisi est l'\emph{ordre produit} ou \emph{ordre de Pareto} (principe d'unanimit\'e). Intuitivement : $x$ domine $y$ si et seulement si pour tous les crit\`eres les valeurs de $x$ sont meilleures ou 
\'equivalentes \`a celle de $z$ (avec au minimum une relation dominante). Soit : 
\begin{definition}
On consid\`ere le produit cart\'esien de $n$ ensembles $\mathcal{A}_{1},\mathcal{A}_{2},\ldots,\mathcal{A}_{n}$. Si chaque $\mathcal{A}_{i}$ est muni d'un ordre strict $\preceq_{i}$, 
alors \textbf{l'ordre produit} $\preceq_{\times}$ est d\'efini par : $(a_{1},a_{2},\ldots,a_{n})\preceq_{\times} (b_{1},b_{2},\ldots,b_{n})$ ssi :
\begin{itemize}
\item $\forall i\in[1,n],a_{i}\preceq_{i} b_{i}$ ou $a_{i}=b_{i}$ et
\item $\exists j\in[1,n],a_{j}\preceq_{j} b_{j}$
\end{itemize}
\end{definition}
Lorsque $a\preceq b$ on emploiera indiff\'eremment les expressions suivantes : $a$ domine $b$, $a$ contient $b$, $a$ est sup\'erieur \`a $b$, $a$ est plus grand que $b$. \\
Si on applique cet ordre produit au produit cart\'esien $\mathcal{A}_{1}\times\mathcal{A}_{2}\times\ldots\times\mathcal{A}_{n}$, tandis que $\mathcal{A}_{i}$ est muni d'une fonction de pr\'ef\'erence monotone, quelque soit $i$ 
compris entre $1$ et $n$, alors on obtient un ordre partiel. Cet ordre partiel est utilis\'e dans PosNet pour construire un graphe. Ce graphe constitue la structure de donn\'ees distribu\'ee exploit\'ee par PosNet pour optimiser les recherches. 

\subsubsection{Construction du pograph}\label{susubsec:graphesemantique}
%{[}SSRN-id870269]
Le pograph peut \^etre consid\'er\'ee comme une variante du diagramme de Hasse. Le \emph{diagramme de Hasse} de $(E,\preceq)$ est une repr\'esentation graphique d'un ordre fini, 
contenant toutes les informations concernant la relation d'ordre repr\'esent\'ee. $\forall(x,y)\in E^{2}$, $x$ domine $y$ ($x\preceq y$) si et seulement si partant du sommet $x$, on peut 
atteindre le sommet $y$ en montant le long des ar\^etes. Un diagramme de Hasse se construit de la fa\c con suivante :
\begin{itemize}
\item Chaque \'el\'ement de l'ensemble est repr\'esent\'e par un noeud ;
\item Si un \'el\'ement $x$ est plus grand qu'un autre \'el\'ement $y$ selon $\preceq$, on place la repr\'esentation de $x$ plus haut que celle de $y$ ; 
\item La relation entre deux \'el\'ements est mat\'erialis\'ee par un arc entre leurs deux noeuds. Du fait de la disposition des noeuds, il n'est pas utile de dessiner les fl\^eches 
(le diagramme 
est un graphe dirig\'e acyclique) ;
\item Afin de ne pas charger le sch\'ema, on ne repr\'esente pas l'int\'egralit\'e de la relation d'ordre, mais uniquement sa r\'eduction r\'eflexive transitive : 
d'une part, si $x\preceq y$ mais qu'il 
existe $z$ diff\'erent de $x$ et de $y$ tel que $(x\preceq z)$ et $(z\preceq y)$, alors on ne trace pas l'arc entre $x$ et $y$ ; d'autre part, on ne repr\'esente pas les arcs d'un \'el\'ement 
vers lui-m\^eme. 
\end{itemize}
\vspace{0.6cm}
Le pograph est d\'efini \`a partir de l'ensemble des donn\'ees muni de la relation d'ordre produit. De mani\`ere analogue au diagramme de Hasse 
de $(\mathcal{S}_{\mathcal{O}}, \preceq)$, 
dans le pograph de $(\mathcal{S}_{\mathcal{O}},\preceq)$ les noeuds sont les \'el\'ements de $\mathcal{S}_{\mathcal{O}}$ et deux noeuds sont adjacents si et seulement s'ils sont 
comparables. L\`a o\`u le pograph se distingue fondamentalement du diagramme de Hasse c'est par l'ajout d'arcs suppl\'ementaires et par l'\'etiquetage des arcs. Ces modifications 
%se justifient par la recherche de chemins sans vall\'ee au sein du graphe, comme on va le voir en \ref{cheminssansvallee}).  
sont introduites pour ajouter des propri\'et\'es au graphe et garantir ainsi, \`a la diff\'erence du diagramme de Hasse, l'existence des chemins sans vall\'ee au sein du pograph (cf. plus bas section \ref{subsubsec:Chemins sans vall\'ee dans le pograph}).  
%
%des propri\'et\'es au graphe. Comme  \ref{subsubsec:Chemins sans vall\'ee dans le pograph}, \`a la diff\'erence du diagramme de Hasse, on va pouvoir garantir l'existence de chemins sans vall\'ee au sein du pograph.  

Pour chaque noeud $s$ d'un pograph, on d\'efinit un ensemble de \emph{parents}, not\'e ${parents}(s)$ qui est l'ensemble des plus petits majorants de $s$. Le noeud $s$ est 
reli\'e \`a ses parents par des arcs ascendants $\xrightarrow{\prec}$ appel\'es arcs c2p (pour << child to parent >>). 
Sym\'etriquement, on d\'efinit pour chaque noeud $s$ un ensemble d'\emph{enfants}, not\'e ${enfants}(s)$, compos\'e des plus grands minorants de $s$. $s$ est reli\'e \`a ses enfants 
par des arcs descendants $\xrightarrow{\succ}$ appel\'es arcs p2c (pour << parent to child >>). 
Les noeuds associ\'es aux solutions maximales sont organis\'es en une clique (graphe complet). \`A propos de cette clique des solutions maximales, on emploiera parfois la d\'enomination 
de \emph{noyau}. On d\'efinit pour chaque noeud $s$ du noyau, un ensemble de \emph{co-maximaux}, not\'e ${comax}(s)$ qui est l'ensemble des autres noeuds appartenant au noyau. 
$s$ est reli\'e \`a ses co-maximaux par un arc plat $\xrightarrow{\sim}$ appel\'es arcs m2m (pour << maximal to maximal >>). Pour un noeud $s$ quelconque, ${parents}(s)$, ${enfants}(s)$ ou ${comax}(s)$ peuvent \^etre vides. Mais s'il existe au moins deux solutions diff\'erentes au total, alors chaque n\oe ud
dispose au moins d'un enfant d'un parent et d'un comax. 
%Mais s'il existe au moins deux solutions diff\'erentes 

Plus formellement, on d\'efinit le pograph de la fa\c con suivante : 

\begin{definition}
Le \textbf{pograph} est un graphe dirig\'e avec des labels port\'es par les arcs. Ce digraphe est un graphe sym\'etrique o\`u pour
chaque arc $\overrightarrow{(a,b)}$, l'arc $\overrightarrow{(b,a)}$ existe et il porte le label sym\'etrique du label de l'arc
$\overrightarrow{(a,b)}$. Un graphe 
sym\'etrique est donn\'e par un ensemble de sommets et un ensemble d'arcs tel que, pour tout $a$ \'el\'ement de $A$, il existe un arc oppos\'e $\overline{a}$ dont l'origine est 
l'extr\'emit\'e de $a$ et dont l'extr\'emit\'e est l'origine de $a$. De plus, 
\begin{itemize}
\item $a \xrightarrow{\succ} b$ et $b \xrightarrow{\prec} a$ ssi $a\in \emph{parents}(b)$
\item $a \xrightarrow{\prec} b$ et $b \xrightarrow{\succ} a$ ssi $a\in \emph{enfants}(b)$ 
\item $a \xrightarrow{\sim} b$ et $b \xrightarrow{\sim} a$ ssi $\nexists u\in \mathcal{S}_\mathcal{O}$ avec $a \prec u$ ou $b \prec u$.
\end{itemize}
\end{definition}

Soit $E=((3,2),(2,5),(3,5),(1,9),(4,9),(8,10),(9,9),(10,1),(9,4),(7,3),(9,1),(4,2))$, muni de la relation d'ordre produit d\'enot\'ee $\preceq$, la figure \ref{fig:diaggrapheexemple} 
illustre les diagramme de Hasse (\ref{subfig:hasseexemple}) et pograph (\ref{subfig:graphesemantiqueexemple}) associ\'es. 

\begin{figure}[!h]

	\begin{center}
  \subfigure[Diagramme de Hasse de $(E,\preceq)$]
  {\epsfig{file=fig/hasse_exemple,scale=0.6}\label{subfig:hasseexemple}}
  $\,$
	\subfigure[Graphe s\'emantique de $(E,\preceq)$.]
	{\epsfig{file=fig/graphe_semantique_exemple,scale=0.6}\label{subfig:graphesemantiqueexemple}}
	\end{center}
	%\label{fig:diaggrapheexemple}
	\caption{TODO corriger les labels + franglais !!! /// Comparaison entre le diagramme de Hasse et le pograph de $(E,\preceq)$}
	\label{fig:diaggrapheexemple}
\end{figure}

\subsection{Chemins sans vall\'ee}\label{subsubsec:Chemins sans vallee}
L'organisation en clique des \'el\'ements maximaux conf\`ere une propri\'et\'e structurelle importante au pograph : elle garantit l'existence d'au moins un \emph{chemin sans 
vall\'ee}\footnote{L'appellation \og sans vall\'ee \fg{} des chemins emprunte au domaine des r\'eseaux TCP/IP. Gao, la premi\`ere, d\'efinit dans \cite{gao01inferring} le mod\`ele des chemins sans vall\'ee appliqu\'e au routage BGP.
 Comme dans un r\'eseau de syst\`emes autonomes (AS), le routage dans PosNet d\'efinit la validit\'e des chemins selon l'absence ou la pr\'esence de \og vall\'ee \fg{}. Comme dans un r\'eseau d'AS, l'absence de \og 
vall\'ee \fg{} dans les chemins emprunt\'es par le trafic Internet est un effet de bord des politiques de routage. Mais l'analogie s'arr\^ete-l\`a : les r\'eseaux d'AS inhibent les circuits 
fournisseur-client-fournisseur pour des raisons \'economiques, tandis que PosNet inhibe les circuits parent-enfant-parent pour des raisons algorithmiques.
} entre toute paire de noeuds s\'emantiques. 
\begin{definition}
Un \textbf{chemin sans vall\'ee} se compose d'une s\'equence de $i \geq 0$ arcs ascendants, puis \'eventuellement d'un unique arc plat et se termine par une s\'equence 
de $k \geq 0$ arcs descendants. 
%Un tel chemin est plus pr\'ecis\'ement d\'efini comme un chemin sans vall\'ee-$(i,j,k)$ de taille $i+j+k$. 
\end{definition}


Par commodit\'e, on qualifie de \emph{chemin ascendant} (resp. \emph{descendant}) une s\'equence d'arcs ascendants (resp. descendants). 
Intuitivement, dans une s\'equence d'arcs une vall\'ee se caract\'erise par un arc descendant suivi d'un arc ascendant ou plat, ou bien par un arc plat suivi d'un arc ascendant ou plat. 
Un chemin sans vall\'ee est un chemin dont la s\'equence d'arcs constitutive ne comporte pas de \og vall\'ee \fg{}. Dans le cadre de PosNet, un chemin est dit valide si et seulement si 
c'est un chemin sans vall\'ee. Le chemin est dit invalide sinon. La figure \ref{fig:Reglescomposition} illustre les r\`egles de composition des arcs lors du parcours d'un pograph \`a l'aide de chemins sans vall\'ee.

\begin{figure}[!h]
\begin{center}
\epsfig{file=fig/chemin_sans_vallee_automate,scale=0.6}
\label{fig:Reglescomposition}
\caption{TODO \`a franciser /// R\`egles de compositions des arcs dans un chemin sans vall\'ee}
\end{center}
\end{figure} 

La figure \ref{fig:exemplecheminsansvallee} donne un exemple de chemin sans vall\'ee que l'on peut obtenir en appliquant ces r\`egles, sur l'exemple jouet de la figure \ref{fig:diaggrapheexemple}. 

\begin{figure}[!]
	\centering
	%\includegraphics[width=0.6\textwidth]{./fig/quadtree_ang.jpg}
		\includegraphics[width=0.4\textwidth] {fig/exemplecheminsansvallee}
		\caption{TODO refaire avec labels corrig\'es /// Exemple de chemin sans vall\'ee dans un pograph bidimensionnel entre les donn\'ees $(2,5)$ et $(9,4)$}
\label{fig:exemplecheminsansvallee}
\end{figure}

% \begin{floatingfigure}[option]{8cm}
% 	\centering
% 	%\includegraphics[width=0.6\textwidth]{./fig/quadtree_ang.jpg}
% 		\includegraphics[width=0.3\textwidth]{fig/exemplecheminsansvallee}
% 		\caption{TODO refaire avec labels corrig\'es /// Exemple de chemin sans vall\'ee dans un pograph bidimensionnel entre les donn\'ees $(2,5)$ et $(9,4)$}
% \label{fig:fonctionnementIndex}
% \end{floatingfigure}

\begin{lemma} \label{existencechemin}
Etant donn\'es deux sommets $x$ et $y$ quelconques d'un pograph, il existe au moins un chemin sans vall\'ee reliant $x$ \`a $y$.
\end{lemma}

%La d\'emonstration de l'existence d'au moins un chemin sans vall\'ee entre deux sommets quelconques d'un pograph repose sur la notion de 
%\emph{cha\^ine}, dont voici la d\'efinition : 
%\begin{definition}
%Un ensemble $\mathcal{E}$ muni d'un ordre partiel. $\mathcal{E}$ est dit totalement ordonn\'e si et seulement si $ \forall (x,y) \in \mathcal{E}^2 x \leq y \lor y \leq x$. Un ensemble totalement ordonn\'e est aussi appel\'e une \textbf{cha\^ine}. 
%\end{definition}
%En d'autres termes, une cha\^ine est une s\'equence d'arcs ascendants ou une s\'equence d'arcs descendants, et forme en tant que telle un chemin sans vall\'ee. Nous pouvons maintenant \'enoncer la preuve suivante du lemme \ref{existencechemin} : 

Si l'on d\'efinit une \emph{cha\^ine} comme un ensemble totalement ordonn\'e\footnote{Soit un ensemble $\mathcal{E}$ muni d'un ordre partiel, $\mathcal{E}$ est dit totalement ordonn\'e si et seulement si $ \forall (x,y) \in \mathcal{E}^2 x \leq y \lor y \leq x$.} (et donc un chemin sans vall\'ee), alors on peut \'enoncer la preuve suivante du lemme : 

\begin{proof}
Soit un pograph construit \`a partir d'un ensemble $\mathcal{E}$ muni d'un ordre partiel. Soient $x$ et $y$ deux \'el\'ements de $\mathcal{E}$. Deux cas se pr\'esentent : ou bien $x$ et $y$ sont comparables ou bien $x$ et $y$ sont incomparables. Si $x$ et $y$ sont comparables, alors il existe une cha\^ine $C$ dans $E$ telle que $x$ et $y$ appartiennent \`a $C$. Il existe alors un chemin sans vall\'ee entre $x$ et $y$ sous la forme d'une sous-cha\^ine $C'$ de $C$ reliant $x$ et $y$.
Si $x$ et $y$ sont incomparables, alors $x$ et $y$ appartiennent \`a des cha\^ines $C_x$ et $C_y$ de $\mathcal{E}$ distinctes. Les \'el\'ements maximaux $m_{C_x}$ et $m_{C_y}$ de chaque cha\^ine appartiennent au noyau, par d\'efinition du noyau. Les \'el\'ements du noyau \'etant connect\'es en clique, il existe alors un chemin sans vall\'ee reliant $x$ et $y$ form\'e d'une sous-cha\^ine $C'_x$ allant de $x$ \`a $m_{C_x}$, puis en saut de $m_{C_x}$ \`a $m_{C_y}$ et enfin de $m_{C_y}$ \`a $y$.  
\qedhere
\end{proof}
\vspace{0.6cm}

Si le graphe complet des solutions maximales garantit l'existence d'au moins un chemin sans vall\'ee entre deux noeuds du pograph, il est important de remarquer qu'un chemin sans vall\'ee ne passe pas obligatoirement par le noyau. 
Lorsque $x$ et $y$ poss\`ede plusieurs majorants, il existe un plus court chemin sans vall\'ee les reliant qui passe par le plus petit majorant. Si ce plus petit majorant n'est pas un 
noeud maximal, alors le chemin ne passe pas par le noyau. 

%Si $a$ et $b$, deux noeuds du pograph, ont des majorants en commun (hors noeuds maximaux), alors il existe au moins un chemin sans vall\'ee reliant $a$ et $b$ qui passe par 
%le plus petit majorant, et ce chemin est plus court que le chemin passant par le noyau.\\
%A basic but fundamental property of the graph $\mathcal{G}_\mathcal{O}$ is that data content \emph{locality} is preserved: similar data are located closely in the graph topology 
%(two points $a$ and $b$ are adjacent in the graph when $a$ is a least upper bound ($\emph{lub}$) or a greatest lower bound ($\emph{glb}$) of $b$).

\vspace{1cm}
\section*{Conclusion}

La premi\`ere partie de ce chapitre a permis de rappeler les motivations de ce travail et d'en sp\'ecifier les contributions. La seconde partie a pr\'esent\'e une vue statique de l'architecture g\'en\'erale de la solution propos\'ee, PosNet, et a 
couvert enti\`erement la premi\`ere contribution en sp\'ecifiant la structure de donn\'ees principale de PosNet : le pograph. 
Nous avons vu comment le pograph permet, en exploitant une relation d'ordre partiel d\'efinie sur l'ensemble des donn\'ees, d'organiser celles-ci en un graphe garantissant l'existence d'au moins un chemin sans vall\'ee entre deux sommets quelconques du graphe. Les chapitre suivants se consacrent \`a la d\'emonstration de l'utilit\'e de ses chemins sans vall\'ee dans l'optimisation des recherches exactes, par intervalles et skyline (chapitre \ref{chap:Plan de transfert des requ\^etes}) et \`a a la faisabilit\'e de
ce mod\`ele d'index dans un environnement distribu\'e dynamique (chapitre \ref{chap:Plan de contr\^ole}).   
